// from https://www.cnblogs.com/KillerAery/p/9231511.html

#include <iostream>
#include <list>
#include <queue>
#include <random>
#include <vector>

const int width = 30;          // 地图长度
const int height = 100;        // 地图高度
char mapBuffer[width][height]; // 地图数据
int depth = 0;                 // 记录深度
const int depthLimit = 2000;   // 深度限制

struct OpenPoint {
  int x;
  int y;
  int cost;      // 耗费值
  int pred;      // 预测值
  size_t father; // 父节点索引值
  OpenPoint() = default;
  OpenPoint(int pX, int pY, int endX, int endY, int c, size_t fatherIndex)
      : x(pX), y(pY), cost(c), father(fatherIndex) {
    // 相对位移x,y取绝对值
    int relativeX = std::abs(endX - pX);
    int relativeY = std::abs(endY - pY);
    // x,y偏移值n
    int n = relativeX - relativeY;
    // 预测值pred = (max–n)*14+n*10+c
    this->pred = std::max(relativeX, relativeY) * 14 - std::abs(n) * 4 + c;
  }
};

// 存储OpenPoint的内存空间
std::vector<OpenPoint> pointPool;
// 创建一个开启点
size_t createOpenPoint(int pX, int pY, int endX, int endY, int c,
                       size_t fatherIndex) {
  pointPool.emplace_back(OpenPoint(pX, pY, endX, endY, c, fatherIndex));
  return pointPool.size() - 1;
}

// 记录障碍物+关闭点的二维表
bool closeAndBarrierList[width + 1][height + 1];
// 是否在障碍物或者closelist
bool inBarrierAndCloseList(int pX, int pY) {
  if (pX < 0 || pY < 0 || pX >= width || pY >= height)
    return true;
  return closeAndBarrierList[pX][pY];
}

// 比较器，用以优先队列的指针类型比较
struct OpenPointCompare {
  bool operator()(size_t a, size_t b) {
    return pointPool[a].pred > pointPool[b].pred;
  }
};
// openlist 使用最大优先队列
std::priority_queue<size_t, std::vector<size_t>, OpenPointCompare> openlist;

// 开启检查 openPoint
void open(size_t openPointIndex, int endX, int endY) {
  int px = pointPool[openPointIndex].x;
  int py = pointPool[openPointIndex].y;
  // 如果目标在障碍物或者closelist
  if (inBarrierAndCloseList(px, py)) {
    return;
  }
  // 移入closelist···
  closeAndBarrierList[px][py] = true;

  // openPoint的开销
  int pcost = pointPool[openPointIndex].cost;
  // 八个方向以及方向对应的开销
  const int dir[8][2] = {{1, 0}, {0, 1},  {-1, 0},  {0, -1},
                         {1, 1}, {-1, 1}, {-1, -1}, {1, -1}};
  const int cost[8] = {10, 10, 10, 10, 14, 14, 14, 14};
  // 检查p点八方的点
  for (int i = 0; i < 8; ++i) {
    int toOpenX = px + dir[i][0];
    int toOpenY = py + dir[i][1];
    openlist.push(createOpenPoint(toOpenX, toOpenY, endX, endY, pcost + cost[i],
                                  openPointIndex));
  }
}

// 开始搜索路径
std::list<size_t> findway(int startX, int startY, int endX, int endY) {
  // 创建并开启一个父节点
  openlist.push(createOpenPoint(startX, startY, endX, endY, 0, -1));
  size_t endIndex = -1;
  // 重复寻找预测和花费之和最小节点开启检查
  while (!openlist.empty()) {
    // 深度+1
    depth++;
    // 若超出一定深度，则搜索失败
    if (depth >= depthLimit) {
      return std::list<size_t>();
    }

    size_t openPointIndex = openlist.top();
    // 将父节点从openlist移除
    openlist.pop();

    // 找到终点后，则停止搜索
    if (pointPool[openPointIndex].x == endX &&
        pointPool[openPointIndex].y == endY) {
      endIndex = openPointIndex;
      break;
    }
    open(openPointIndex, endX, endY);
  }
  // 返还一条路径
  std::list<size_t> road;
  for (size_t index = endIndex; index != -1; index = pointPool[index].father) {
    road.push_back(index);
  }
  return road;
}

// 创建地图
void createMap() {
  std::random_device rd;  // a seed source for the random number engine
  std::mt19937 gen(rd()); // mersenne_twister_engine seeded with rd()
  std::uniform_int_distribution<> distrib(1, 5);

  for (int i = 0; i < width; ++i)
    for (int j = 0; j < height; ++j) {
      // 五分之一概率生成障碍物，不可走
      if (distrib(gen) == 1) {
        mapBuffer[i][j] = '*';
        closeAndBarrierList[i][j] = true;
      } else {
        mapBuffer[i][j] = ' ';
        closeAndBarrierList[i][j] = false;
      }
    }
}

// 打印地图
void printMap() {
  for (int i = 0; i < width; ++i) {
    for (int j = 0; j < height; ++j)
      std::cout << mapBuffer[i][j];
    std::cout << '\n';
  }
  std::cout << '\n' << '\n' << '\n';
}

int main() {
  // 起点
  int beginX = 0;
  int beginY = 0;
  // 终点
  int endX = 29;
  int endY = 99;
  // 创建地图
  createMap();
  // 保证起点和终点都不是障碍物
  mapBuffer[beginX][beginY] = mapBuffer[endX][endY] = ' ';
  closeAndBarrierList[beginX][beginY] = closeAndBarrierList[endX][endY] = false;
  // A*搜索得到一条路径
  std::list<size_t> road = findway(beginX, beginY, endX, endY);
  // 将A*搜索的路径经过的点标记为'O'
  for (size_t index : road) {
    mapBuffer[pointPool[index].x][pointPool[index].y] = 'O';
  }
  // 打印走过路后的地图
  printMap();
  system("pause");
  return 0;
}